package com.my.algorithmlearning.leetcode;

import org.springframework.util.Assert;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ClassName MajorityElement
 * @Description MajorityElement
 * @Author wanghaiwei
 * @Date 2023/1/6 10:01
 */
public class MajorityElementN3 {

    public List<Integer> majorityElement(int[] nums) {
        int candidate1 = 0,candidate2 = 0;
        int votes1 = 0,votes2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if(candidate1 == nums[i]) {
                votes1++;
            }else if (candidate2 == nums[i]) {
                votes2++;
            }else if (votes1 == 0) {
                candidate1 = nums[i];
                votes1++;
            }else if(votes2 == 0) {
                candidate2 = nums[i];
                votes2++;
            }else {
                votes1--;
                votes2--;
            }
        }
        int thredhold = (int) (nums.length / 3.0);
        List<Integer> results = new ArrayList<>();
        if (votes1 > thredhold) {
            results.add(candidate1);
        }
        if (votes2 > thredhold) {
            results.add(candidate2);
        }
        return results;
    }

    public static boolean resultIsCorrect(int[] expect, int[] actual) {
        Arrays.sort(expect);
        Arrays.sort(actual);
        return Arrays.equals(expect, actual);
    }

    public static void main(String[] args) {
        MajorityElementN3 solution = new MajorityElementN3();
        Assert.isTrue(resultIsCorrect(new int[]{3}, solution.majorityElement(new int[]{3,2,3}).stream().mapToInt(Integer::intValue).toArray()), "majorityElement nums = [3,2,3]计算失败");
        Assert.isTrue(resultIsCorrect(new int[]{1},solution.majorityElement(new int[]{1}).stream().mapToInt(Integer::intValue).toArray()), "majorityElement nums = [1]计算失败");
        Assert.isTrue(resultIsCorrect(new int[]{1,2},solution.majorityElement(new int[]{1,2}).stream().mapToInt(Integer::intValue).toArray()), "majorityElement nums = [1,2]计算失败");
        Assert.isTrue(resultIsCorrect(new int[]{1,2},solution.majorityElement(new int[]{2,2,1,1,1,2,2}).stream().mapToInt(Integer::intValue).toArray()), "majorityElement nums = [2,2,1,1,1,2,2]计算失败");
        Assert.isTrue(resultIsCorrect(new int[]{2},solution.majorityElement(new int[]{2,2,1,3}).stream().mapToInt(Integer::intValue).toArray()), "majorityElement nums = [2,2,1,1,1,2,2]计算失败");
    }
}
